Algorithmic Thinking, 2nd Edition (for Tinh Hong) by Daniel Zingaro

Author:Daniel Zingaro
Language: eng
Format: epub
Publisher: No Starch Press, Inc.
Published: 2024-11-15T00:00:00+00:00

Two Optimizations

There are a few things that can be done to speed up Dijkstra’s algorithm. The most widely applicable and dramatic speedup is wrought by a data structure called a heap. In our current implementation, it’s very expensive to find the next node to set to done, as we need to scan through all nodes that are not done to find the one with the shortest path. A heap uses a tree to convert this slow, linear search into a fast search. As heaps are useful in many contexts beyond Dijkstra’s algorithm, I’ll discuss them later, in Chapter 8. Here, I’ll offer a couple of optimizations more specific to the Mice Maze problem.

Recall that as soon as a cell is done, we never change its shortest path again. As such, once we set the exit cell to done, we have its shortest path. After that, there’s no reason to find shortest paths for other cells. We may as well terminate Dijkstra’s algorithm early.

We can still do better, though. For a maze of n cells, we invoke Dijkstra’s algorithm n times, once for each cell. For Cell 1, we compute all shortest paths—and then keep only the shortest path to the exit cell. We do the same for Cell 2, Cell 3, and so on, throwing out all of the shortest paths we found except for those that involve the exit cell.

Instead, consider running Dijkstra’s algorithm just once, with the exit cell as the starting cell. Dijkstra’s algorithm would then find the shortest path from the exit cell to Cell 1, the exit cell to Cell 2, and so on. However, that’s not quite what we want, because the graph is directed: the shortest path from the exit cell to Cell 1 is not necessarily the shortest path from Cell 1 to the exit cell.

Here again is Figure 6-1:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.